#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;

//盈利计划
//https://leetcode.cn/problems/profitable-schemes/description/
//class Solution {
//public:
//    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
//        //dp[i][j][k]表示从前i个利润中选择 总人数不超过n 例如超过minProfit的 一共有多少种选法
//        const int MOD = 1e9 + 7;
//        int len = group.size();
//
//        vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));
//
//        //当人数为0时 无法产生利润 只有一种选法 那就是不选
//        for (int i = 0; i <= n; ++i) dp[0][i][0] = 1;
//
//        for (int i = 1; i <= len; ++i) //利润
//            for (int j = 0; j <= n; ++j) //人数
//                for (int k = 0; k <= minProfit; ++k)
//                {
//                    dp[i][j][k] = dp[i - 1][j][k];
//                    if (j >= group[i - 1])
//                        dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];
//                    dp[i][j][k] %= MOD;
//                }
//
//        return dp[len][n][minProfit];
//    }
//};
//优化
//class Solution {
//public:
//    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
//        const int MOD = 1e9 + 7;
//        int len = group.size();
//
//        vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));
//
//        for (int i = 0; i <= n; ++i) dp[i][0] = 1;
//
//        for (int i = 1; i <= len; ++i) //利润
//            for (int j = n; j >= group[i - 1]; --j) //人数
//                for (int k = minProfit; k >= 0; --k)
//                    dp[j][k] = (dp[j][k] += dp[j - group[i - 1]][max(0, k - profit[i - 1])]) % MOD;
//
//        return dp[n][minProfit];
//    }
//};


//组合总和IV
//https://leetcode.cn/problems/combination-sum-iv/description/
// class Solution {
// public:
//     int combinationSum4(vector<int>& nums, int target) {
//         int n = nums.size();
//         //dp[i] 选择i数后 从其他数中选择凑出总和为target 一共有多少种排列数
//         vector<double> dp(target+1);
//         dp[0] = 1; //要选出组合为0的组数 只有一种可能 那就是不选

//         for(int i = 1;i<=target;++i)
//             for(int k = 0;k<n;++k)
//                 //当我们选择i之后 只需要知道i-nums[k]有多少种凑法即可
//                 if(i >= nums[k]) dp[i] += dp[i-nums[k]];

//         return dp[target];
//     }
// };


//不同的二叉搜索树
//https://leetcode.cn/problems/unique-binary-search-trees/
// class Solution {
// public:
//     int numTrees(int n) { //卡特兰数
//         //dp[i]表示选择i为节点时二叉搜索树的种数
//         vector<int> dp(n+1);
//         dp[0] = 1; //空树是一种选法
//         for(int i = 1;i<=n;++i) //当前二叉树的节点总数
//             for(int k = 1;k<=i;++k) //根节点
//                 //总数是 二叉树 根节点 右边的节点总数*左边节点总数
//                 dp[i] += dp[i-k]*dp[k-1];

//         return dp[n];
//     }
// };